\documentclass{beamer}
\usepackage{graphicx}
\graphicspath{{./gfx/}}
\usepackage{url}
\usepackage{beamerthemeshadow}
\usepackage{listings}

\newcommand{\bullets}[1]{\begin{itemize} #1 \end{itemize}}
\newcommand{\deflist}[1]{\begin{description} #1 \end{description}}
\newcommand{\ttt}[1]{\texttt{#1}}

\begin{document}
\title{Analysis of the GMP Library}  
\author{Lingchuan Meng\\ 
	Don Naegely\\
	Abizer Nayeem\\
	Joydeep Tripathi}
\date{\today} 

\frame{\titlepage} 

%\frame{\frametitle{Table of contents}\tableofcontents} 

\section{Introduction}

\subsection{Background}
\frame{\frametitle{How does GMP store number?}
\bullets{
	\item Each multi-precision number broken up into array of limbs.
	\item Limb size defined as largest portion of number fitting in single word.
	\item Size is usually 32- or 64-bit.
	\item Size found to be 64-bit on our machine.
	\item Each limb can store numbers up to $2^{64}=18446744073709551616$.
	\item Limbs stored in little endian format.
}
}

\subsection{Algorithms}
\frame{\frametitle{Overview}
GMP uses 4 multiplication algorithms:
	\begin{enumerate}
	 \item Base Case
	 \item Karatsuba's
	 \item Toom 3
	 \item FFT
	\end{enumerate}
A more detailed explanation of these algorithms can be found in our report.
}

\subsection{Performance Analysis}
\frame{\frametitle{Performance Analysis}
\bullets{
	\item Because of speed of GMP operations, most test numbers were millions of digits long.
	\item Used \ttt{mpz\_urandomm()} to generate these numbers.
	\item Bulk of test time is in random number generation.
	\item Also, extra overhead from running each operation 20 times to get minimum results.
	\item Focused on large integer addition, large integer multiplication, and threshold multiplication.
}
}

\section{Addition}
\subsection{Test Details}
\frame{\frametitle{Test Details}
Our tests measured the following for integer addition in the range 10 million to 410 digits with a step size of 20 million digits. 
\bullets {
	\item Number of Limbs
	\item Total Instructions(PAPI)
	\item Total Cycles(PAPI)
	\item L1 Data Cache Misses(PAPI)
	\item L2 Data Cache Misses(PAPI)
	\item Time(sec)
}
}
\subsection{Data}
\frame{\frametitle{Raw Data}
\begin{table}[h!]
\caption{Performance of mpz\_add()}
\centering
{\tiny
\begin{tabular}{ccccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM & Time(s)\\
\hline
10000000&519052&3114675&12420788&194682&68928&0\\
30000000&1557154&9343305&31853459&583979&203683&0.01\\
50000000&2595257&15571923&52881345&973278&311426&0.02\\
70000000&3633359&21800540&70503638&1362573&410995&0.03\\
90000000&4671462&28029169&114465743&1751901&547342&0.06\\
110000000&5709564&34257785&139385241&2141201&660982&0.07\\
130000000&6747667&40486412&169436362&2530519&873990&0.09\\
150000000&7785769&46715010&157499346&2808543&1024995&0.08\\
170000000&8823872&52943655&224273396&3309129&1290422&0.12\\
190000000&9861975&59172275&238344190&3695066&1275609&0.13\\
210000000&10900077&65400890&265252953&4087729&1397094&0.14\\
230000000&11938180&71629493&246563451&4458146&1561205&0.13\\
250000000&12976282&77858112&285995023&4866276&1768416&0.16\\
270000000&14014385&84086731&297947395&5215292&1816044&0.16\\
290000000&15052487&90315384&337673045&5640000&1249309&0.19\\
310000000&16090590&96543987&403008952&6031785&1254973&0.22\\
330000000&17128692&102772606&429520242&6421092&1340267&0.24\\
350000000&18166795&109001232&456801304&6810467&1421332&0.25\\
370000000&19204897&115229848&483314023&7199044&1506141&0.26\\
390000000&20243000&121458466&509808296&7590679&1591551&0.27\\
\hline
\end{tabular}
}
\label{table:mpz_add}
\end{table}
}
\subsection{Graphs}
\frame{\frametitle{Limbs vs. Instructions Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_instructions.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. Cycles Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_cycles.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. L1 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_l1_dcm.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. L2 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_l2_dcm.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. Time Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_time.png}
\end{figure}
}

\section{Large Integer Multiplication}
\subsection{Introduction}
\frame{\frametitle{Introduction}
During the testing of large integer multiplication, we gathered the same data as in the addition portion of the tests but for a new range of 10 million digits to 41 million digits with a step size of 2 million digits. Since the FFT threshold, the highest of the three, was quite low, thresholds were not a factor in this portion of the testing and are addressed further in \S \ref{ssec:threshold_intro}.
}
\subsection{Data}
\frame{\frametitle{Raw Data}
\begin{table}[h!]
\caption{Performance of mpz\_mul()}
\centering
{\tiny
\begin{tabular}{ccccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM & Time(s)\\
\hline
1000000&51906&261498331&170597905&898928&335538&0.09\\
3000000&155716&859016747&599195719&2827366&1550409&0.33\\
5000000&259526&1782446873&1180892420&5103760&3057592&0.65\\
7000000&363336&2794878390&1755146686&7141708&4442197&0.97\\
9000000&467147&3377123614&2340735509&11345685&6464459&1.3\\
11000000&570957&4578335293&3039064246&14390154&8367755&1.7\\
13000000&674767&5963633580&3891119823&18210364&10785654&2.16\\
15000000&778577&6739293261&4147220039&20282261&9813210&2.33\\
17000000&882388&7165035593&4779309353&22240031&10738858&2.68\\
19000000&986198&8517356187&5544294822&26323941&13433642&3.11\\
21000000&1090008&9154459734&6170050969&27861709&17293747&3.46\\
23000000&1193818&9930343657&6326038069&30578638&15797742&3.57\\
25000000&1297629&10532895160&6680611513&32806431&16915095&3.78\\
27000000&1401439&11039017292&7389728401&34578361&18809525&4.18\\
29000000&1505249&12287390167&8114345217&38230665&21117995&4.6\\
31000000&1609059&12791957866&8539857254&41011290&20439815&4.83\\
33000000&1712870&15057930789&9363347950&50219842&22274665&5.29\\
35000000&1816680&15786572457&10619992782&55546419&25961837&6.01\\
37000000&1920490&15790297291&10648185669&57052883&27791537&6.02\\
39000000&2024300&18948675651&12336267010&64723194&31506660&6.97\\
\hline
\end{tabular}
}
\label{table:mpz_mul}
\end{table}
}

\subsection{Graphs}
\frame{\frametitle{Limbs vs. Instructions Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_instructions.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. Cycles Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_cycles.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. L1 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_l1_dcm.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. L2 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_l2_dcm.png}
\end{figure}
}
\frame{\frametitle{Limbs vs. Time Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_time.png}
\end{figure}
}

\section{Threshold Multiplication}
\subsection{Introduction}
\label{ssec:threshold_intro}
\frame{\frametitle{What Are Thresholds?}
	\bullets{
		\item GMP uses thresholds to determine which multiplication algorithm to use.
		\item Thresholds are represented in limb sizes, that is number of limbs in a number.
		\item Three thresholds exists:
		\bullets{
			\item \ttt{MUL\_KARATSUBA\_THRESHOLD}
			\item \ttt{MUL\_TOOM3\_THRESHOLD}
			\item \ttt{MUL\_FFT\_THRESHOLD}
		}
		\item These are defined in \ttt{gmp-mparam.h} and customized values can be determined by running tuneup in the tune directory.
	}
}
\frame{\frametitle{Threshold Values}
	\bullets{
		\item Threshold values as defined in \ttt{gmp-mparam.h}:
		\bullets{
			\item \ttt{MUL\_KARATSUBA\_THRESHOLD} = 31
			\item \ttt{MUL\_TOOM3\_THRESHOLD} = 105
			\item \ttt{MUL\_FFT\_THRESHOLD} = 4736
		}	
		\item Tuneup program gave different result for FFT threshold but it was ignored. More details can be found in the report.
		\item What number's appear around these thresholds? How can we test these thresholds? 
	}
}
\frame{\frametitle{Determining Threshold Ranges}
	\bullets{
		\item It was shown that a limb can hold all 19 digit and some 20 digit numbers.
		\item If thresholds are as defined in previous slide, then the following graph is a reasonable esitmation of test ranges about the thresholds.
		{\tiny
		\begin{center}
		\begin{tabular}{|c|c|c|c|c|}
			\hline
			\bf Threshold & \bf Limbs & \bf Approx. Digits & \bf Lower Digit Bound & \bf Upper Digit Bound\\
			\hline
			Karatsuba & 31 & 593.817567568 & 589 & 620\\
			\hline
			Toom3 & 105 & 2011.317567568 & 1995 & 2100\\
			\hline
			FFT & 4736 & 90720 & 89984 & 94720\\
			\hline
		\end{tabular}
		\end{center}
		}
		\item Lower bound assumes all limbs are 19 digits, upper bound assumes 20 digits. 
		\item In reality, we have a mix of 19 and 20 digit limbs and we can estimate the average number of digits to be $\frac{1}{1.184} * 19 * L + \frac{0.184}{1.184} * 20 * L$ where $L$ is the number of limbs.
	}
}
\frame{\frametitle{Testing Thresholds}
	\bullets{
		\item Testing values between lower and upper bounds will provide insight into behavior of different algorithms for similar numbers around thresholds.
		\item New method used for generating random numbers to get more precise control over number of digits.
		\item Code in \ttt{generator.cpp} returns string of exact number of digits.
		\item Returned string can be passed to \ttt{mpz\_set\_str()} or \ttt{mpz\_init\_set\_str()} to generate new \ttt{mpz\_t} values.
	}
}

\subsection{Karatsuba Threshold}
\frame{\frametitle{Raw Data}
\begin{table}[h!]
\caption{Performance around MUL\_KARATSUBA\_THRESHOLD}
\centering
	{\tiny
		\begin{tabular}{cccccc}
		\hline\hline
		Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
		\hline
		550&29&9355&4800&5&2\\
		555&29&9355&4800&5&2\\
		560&30&9962&5032&5&2\\
		565&30&9962&5032&5&2\\
		570&30&9962&5032&5&2\\
		\bf 575&\bf 30&\bf 9962&\bf 5032&\bf 5&\bf 2\\
		\bf 580&\bf 31&\bf 9597&\bf 5637&\bf 16&\bf 2\\
		585&31&9597&5640&16&2\\
		590&31&9597&5640&16&2\\
		595&31&9597&5640&16&2\\
		600&32&9967&5762&16&2\\
		605&32&9967&5762&16&2\\
		610&32&9967&5762&16&2\\
		615&32&9967&5762&16&2\\
		620&33&10666&6135&17&2\\
		625&33&10666&6132&17&2\\
		630&33&10666&6135&17&2\\
		635&33&10666&6135&17&2\\
		640&34&11056&6224&18&2\\
		645&34&11056&6224&18&2\\
		\hline
		\end{tabular}
	}
\label{table:tmul_karatsuba}
\end{table}
}
\frame{\frametitle{Karatsuba's Digits vs. Limbs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_karatsuba_limbs.png}
	\end{figure}
}
\frame{\frametitle{Karatsuba's Limbs vs. Counts}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_karatsuba_counts.png}
	\end{figure}
}
\frame{\frametitle{Karatsuba's Limbs vs. DCMs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_karatsuba_dcm.png}
	\end{figure}
}

\subsection{Toom 3 Threshold}
\frame{\frametitle{Raw Data}
	\begin{table}[h!]
	\caption{Performance around MUL\_TOOM3\_THRESHOLD}
	\centering
		{\tiny
			\begin{tabular}{cccccc}
			\hline\hline
			Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
			\hline
			1900&99&66863&32344&4&4\\
			1915&100&67463&32588&4&4\\
			1930&101&69587&33402&8&4\\
			1945&101&69587&33402&8&4\\
			1960&102&70692&33892&15&4\\
			1975&103&71827&34291&8&4\\
			\bf 1990&\bf 104&\bf 72449&\bf 34544&\bf 8&\bf 4\\
			\bf 2005&\bf 105&\bf 70077&\bf 35650&\bf 16&\bf 4\\
			2020&105&70086&35703&16&4\\
			2035&106&72376&36961&16&4\\
			2050&107&73153&37166&15&4\\
			2065&108&73553&37276&15&4\\
			2080&108&73548&37326&15&4\\
			2095&109&75495&38351&21&0\\
			2110&110&75924&38424&21&4\\
			2125&111&76695&38798&21&4\\
			2140&112&79100&40129&21&4\\
			2155&112&79094&40075&21&4\\
			2170&113&79905&40386&21&4\\
			2185&114&80320&40571&20&4\\
			\hline
			\end{tabular}
		}
	\label{table:tmul_toom3}
	\end{table}
}
\frame{\frametitle{Toom 3 Digits vs. Limbs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_toom3_limbs.png}
	\end{figure}
}
\frame{\frametitle{Toom 3 Limbs vs. Counts}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_toom3_counts.png}
	\end{figure}
}
\frame{\frametitle{Toom 3 Limbs vs. DCMs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_toom3_dcm.png}
	\end{figure}
}


\subsection{FFT Threshold}
\frame{\frametitle{Raw Data}
	\begin{table}[h!]
	\caption{Performance around MUL\_FFT\_THRESHOLD}
	\centering
		{\tiny
			\begin{tabular}{cccccc}
			\hline\hline
			Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
			\hline
			85000&4412&21083488&10123361&18800&0\\
			85500&4438&21387829&10235777&18707&0\\
			86000&4464&21616311&10338655&20259&8\\
			86500&4490&21771854&10410464&19839&2\\
			87000&4516&22013472&10504041&19096&3\\
			87500&4542&22180144&10591606&21121&2\\
			88000&4568&22348946&10669201&21226&1\\
			88500&4594&22655580&10787793&20852&5\\
			89000&4620&22872480&10868614&20542&1\\
			89500&4646&23046203&10933816&20796&1\\
			90000&4672&23298978&11038190&21037&1\\
			90500&4698&23473149&11111002&21163&0\\
			\bf 91000&\bf 4724&\bf 23640447&\bf 11183028&\bf 21362&\bf 0\\
			\bf 91500&\bf 4750&\bf 18037297&\bf 9927196&\bf 47510&\bf 0\\
			92000&4776&18039146&9933301&47613&3\\
			92500&4802&19938101&10671776&44245&0\\
			93000&4828&19925875&10665118&44277&0\\
			93500&4854&19942408&10677762&44234&0\\
			94000&4880&19931808&10663479&44224&1\\
			94500&4906&19938770&10669051&44175&0\\
			\hline
			\end{tabular}
		}
	\label{table:tmul_fft}
	\end{table}
}
\frame{\frametitle{FFT Digits vs. Limbs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_fft_limbs.png}
	\end{figure}
}
\frame{\frametitle{FFT Limbs vs. Counts}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_fft_counts.png}
	\end{figure}
}
\frame{\frametitle{FFT Limbs vs. DCMs}
	\begin{figure}[H]
		\centering
			\includegraphics[width=0.8\textwidth]{tmul_fft_dcm.png}
	\end{figure}
}

\end{document}
